#ifndef BINARYSEARCHTREE
#define BINARYSEARCHTREE

#include <iostream>
#include <cstdlib>
namespace algorithm
{
#include <algorithm>
}
#define BLACK false
#define RED true

template <typename T>
class BinarySearchTree
{
 public:
    class Node
    {
    public:
        T data;
	T low;
	T high;
	bool color = RED;
	Node* left;
	Node* right;
	Node* parent;
	Node(T _low,T _high);
	T MAX;
    };
    Node* root;
    Node* nil;
    void inorder_walk(Node* _x) const;
    void release(Node* _x);
    Node* successor(Node* _x) const;
    Node* min(Node* _x) const;
    Node* Max(Node* _x) const;
    Node* predecessor(Node* _x) const;
    void set_low(T _low)
    {
      this->low = _low;
    };
     void set_high(T _high)
    {
      this->high = _high;
    };
    BinarySearchTree() {root = nil;};
    BinarySearchTree(T _low,T _high);
    ~BinarySearchTree();
    void insert(T _low,T _high);
    Node* get_root() const;
    void inorder_walk() const;
    Node* tree_search(T _low, T _high, Node* _x) const;
    void test_successor();
    int transplant(Node *_u, Node *_v);
    int del(Node *_x);
    int del(T _low,T _high);
    int RightRotate(Node* _x);
    int LeftRotate(Node* _x);
};

template <typename T>
void BinarySearchTree<T>::release(Node* _x)
{
  if (_x != this->nil)
    {
	release(_x->left);
	release(_x->right);
	delete _x;
    }	
};

template <typename T>
BinarySearchTree<T>::~BinarySearchTree()
{
    release(root);
};

template <typename T>
BinarySearchTree<T>::Node::Node(T _low,T _high)
{
  data = low = _low;
  high =_high;
  MAX = _high;
  parent = left = right = this->nil;
};

template <typename T>
typename BinarySearchTree<T>::Node* BinarySearchTree<T>::successor(Node* _x) const
{
    Node* x = _x;
    if (x->right != this->nil)
	return min(x->right);
    Node* y = x->parent;
    while (y != this->nil && x == y->right)
    {
	x = y;
	y = y->parent;
    }
    return y;
};

template<typename T>
typename BinarySearchTree<T>::Node* BinarySearchTree<T>::predecessor(Node* _x) const
{
    Node* x = _x;
    if (x->left != this->nil)
	return Max(x->left);
    Node* y = x->parent;
    while (y != this->nil && x == y->left)
    {
	x = y;
	y = y->parent;
    }
    return y;
};


template <typename T>
void BinarySearchTree<T>::test_successor()
{
    std::cout << "successor: " << successor(root->left->left->right)->data << std::endl;
};

template <typename T>
typename BinarySearchTree<T>::Node* BinarySearchTree<T>::min(Node* _x) const
{
    while (_x->left != this->nil)
	_x = _x->left;
    return _x;
};

template <typename T>
typename BinarySearchTree<T>::Node* BinarySearchTree<T>::Max(Node* _x) const
{
    while (_x->right != this->nil)
	_x = _x->right;
    return _x;
};

template <typename T>
typename BinarySearchTree<T>::Node* BinarySearchTree<T>::get_root() const
{
  return root;
};

template <typename T>
void BinarySearchTree<T>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
};

template <typename T>
void BinarySearchTree<T>::inorder_walk(Node* _x) const
{
    if (_x != this->nil)
    {
	inorder_walk(_x->left);
	std::cout << "[" << _x->low << "," << _x->high << "]" << "\t";
	inorder_walk(_x->right);
    }
};

template <typename T>
void BinarySearchTree<T>::insert(T _low,T _high)
{
    Node* y = this->nil;
    Node* x = root;
    Node* p = new Node(_low, _high);
    while (x != this->nil)
    {
	y = x;
	if (p->MAX > x->MAX)
	  x->MAX = p->MAX;
	if (p->data  < x->data)
	    x = x->left;
	else
	    x = x->right;
    }
    p->parent = y;
    if (y == this->nil)
	root = p;
    else if (p->data < y->data)
	y->left = p;
    else
	y->right = p;
};

template <typename T>
typename BinarySearchTree<T>::Node* BinarySearchTree<T>::tree_search(T _low, T _high, Node* _x) const
{
  T _data = _low;
   int flag = 1;
   Node* x = _x;
   if (x != this->nil)
    {
      tree_search(_low, _high, x->left);
	if (x->low == _low && x->high == _high)
	  {
	    if(x == root)
	      {
		std::cout << "Found!" << std::endl;
		flag = 0;
		return x;
	      }
	    else
	      {
		flag = 0;
		return x;
	      }
	  }
        tree_search(_low, _high, x->right);
	if (flag == 1)
	  {
	    if(x == root)
	      {
		std::cout << "Not Found!" << std::endl;
		return x;
	      }
	    else
	      {
		return x;
	      }
	  }
    }
   else
     {
       	if(x == root)
	      {
		std::cout << "Empty BST" << std::endl;
		return 0;
	      }
        else
	      {
		return 0;
	      }	
     }
};

template <typename T>
BinarySearchTree<T>::BinarySearchTree(T _low,T _high)
{
  Node* p = new Node(_low,_high);
    if (root == this->nil)
	root = p;
};

template <typename T>
void BST_sort(T* _head, int _length)
{
  BinarySearchTree<T> tree;
  for (int i = 0; i < _length; i++)
    {
      tree.insert(*(_head + i));
    }
  tree.inorder_walk();
};

template <typename T>
int BinarySearchTree<T>::transplant(Node *_u, Node *_v)
{
  if(_u == nil)
    {
      std::cerr << "Error! Can not transplant to a NULL." << std::endl;
      std::exit(-1);
    }
  if(_u->parent == nil)
    root = _v;
  else if(_u == _u->parent->left)
    {
      _u->parent->left = _v;
      _u->parent->MAX = algorithm::max(_u->parent->high, algorithm::max(_v->MAX,_u->parent->right->MAX));
    }
  else if(_u == _u->parent->right)
    {
      _u->parent->right == _v;
      _u->parent->MAX = algorithm::max(_u->parent->high,algorithm::max(_v->MAX,_u->parent->left->MAX));
    }
  _v->parent = _u->parent;
  return 0;
};

template <typename T>
int BinarySearchTree<T>::del(Node *_x)
{
  if (_x->left == this->nil)
    this->transplant(_x, _x->right);
  else if (_x->right == this->nil)
    this->transplant(_x, _x->left);
  else
    {
      Node *y = min(_x->right);
      if(y->parent != _x)
	{
	  this->transplant(y,y->right);
	  y->right = _x->right;
	  y->right->parent = y;
	}
      this->transplant(_x,y);
      y->left = _x->left;
      y->left->parent = y;
    }
  delete _x;
  return 0;
};

template <typename T>
int BinarySearchTree<T>::del(T _low, T _high)
{
  T _data = _low;
  Node* _x = this->tree_search(_data, this->root);
  if (_x->high == _high)
    {
      if (_x->left == this->nil)
	this->transplant(_x, _x->right);
      else if (_x->right == this->nil)
	this->transplant(_x, _x->left);
      else
	{
	  Node *y = min(_x->right);
	  if(y->parent != _x)
	    {
	      this->transplant(y,y->right);
	      y->right = _x->right;
	      y->right->parent = y;
	    }
	  this->transplant(_x,y);
	  y->left = _x->left;
	  y->left->parent = y;
	}
      delete _x;
    }
  return 0;
};

template <typename T>
int BinarySearchTree<T>::RightRotate(Node *_x)
{
    Node *y = _x->left;
    _x->left = y->right;
    _x->MAX = algorithm::max(_x->MAX, y->right->MAX);
    y->MAX = algorithm::max(y->MAX, _x->MAX);
    if (y->right != nil)
	y->right->parent = _x;
    y->parent = _x->parent;
    if (_x->parent == nil)
	root = y;
    // if _x is _x's parent's left child,
    else if (_x == _x->parent->left)
	// set y as _x's parent's left child.
	_x->parent->left = y;
    else
	_x->parent->right = y;
    y->right = _x;
    _x->parent = y;
};

template <typename T>
int BinarySearchTree<T>::LeftRotate(Node *_x)
{
    Node *y = _x->right;
    _x->right = y->left;
    _x->MAX = algorithm::max(_x->MAX, y->left->MAX);
    y->MAX = algorithm::max(y->MAX, _x->MAX);
    if (y->left != nil)
	y->left->parent = _x;
    y->parent = _x->parent;
    if (_x->parent == nil)
	root = y;
    // if _x is _x's parent's left child,
    else if (_x == _x->parent->left)
	// set y as _x's parent's left child.
	_x->parent->left = y;
    else
	_x->parent->right = y;
    y->left = _x;
    _x->parent = y;
};

#else
//DO NOTHING
#endif
